Contents of memory chips are often corrupted by bit-flips caused by single event upsets. An Error Detection and Correction Code (EDAC code) is commonly used to protect against such errors and preserve the original intended memory content. To implement an EDAC code, a string transmitted to memory is divided into message units which are respectively encoded prior to being put into memory and are then decoded when fetched from memory. The use of EDAC codes is not limited to memory chips. EDAC codes are implemented in many hardware applications wherein the transmitted string risks being corrupted. For example, EDAC codes are implemented to resolve transmission errors found in network communications.
There are several goals in any EDAC implementation:                To maximize effectiveness, as measured by the number of potential errors identified and the number of errors that are corrected automatically;        To maximize speed, equivalent to minimizing a number of processing cycles required;        To minimize other resources required to support the overhead of the EDAC implementation.        
Shu Lin and Daniel J. Costello, in Error Control Coding: Fundamentals and Applications (Prentice-Hall, 1983), categorize, describe and validate mathematically several EDAC implementations. EDAC codes that process each message respectively independent of information found in the other messages are referred to as memory-less. Since memory and other applications of EDAC codes are implemented using digital circuits, typical EDAC codes are binary. Typically, the codes are systematic, i.e., a vector (the coded message) produced by the encoding process comprises both an original input vector (the information message) and additional bits (parity-check bits). In the description below, each coded message is assumed to be n bits long, each information message to be k bits long, (k<n), in which case the number of parity-check bits is n−k; the codes are also referred to as (n,k) codes.
For an (n,k) code there are a total of 2k possible information messages, which an encoder transforms into a set of 2k coded messages, each coded message having a length of n bits. The set of 2k coded messages is referred to as a block code. It will be understood that since n>k, not all of the 2n possible bit combinations map to the 2k possible information messages. The subset of the 2n combinations that do map to the 2k possible information messages are referred to as code words. A linear (n,k) code is a specific type of block code, known in the art, for which encoding complexity is low.
Herein, unless otherwise stated, the terms code, linear code, and EDAC code refer to linear systematic binary EDAC codes.
A distance between any two vectors of a code may be defined as the number of bits that differ in the two vectors. A minimum distance (dmin) of a linear block code is defined as the minimum distance between all permutations of two vectors within the code. An EDAC code in which n−k is large will have a greater dmin than will a code in which n−k is small. That is, dmin is a function of the particular code implemented.
The number of erroneous bits that can be automatically corrected by any specific EDAC implementation (herein known as the error-correcting capability) is typically represented by the letter t.
BCH codes (named for their inventors, Bose, Chaudhuri, and Hocquenghem) provide a robust EDAC implementation, wherein the error-correction value t is typically greater than 1. For example, a subclass of BCH codes possesses the following parameters, wherein m≧3 and t<2m−1, m,t both integers:                Block length (n)=2m−1        Number of parity-check bits: n−k≦mt        information bits (k)=2m−m−1        Minimum distance (dmin)≧2t+1        
For example, if m=7 and t=2, the coded and information message lengths are 127 and 113 bits respectively, 14 parity-check bits are used, and 2 error bits in the information message can be automatically corrected by the code. Inter alia, BCH codes are cyclic codes and thus possess an inherent algebraic structure.
BCH codes, as well as other EDAC codes, may be encoded using a Generator Matrix, as described below. The mapping of the 2k possible information messages, each of length k, to the 2k code words, each of length n, can be described mathematically as a vector matrix multiplication:
Let u represent an information message; u is a row vector of length k;
Let v represent the code word assigned to u; v is a row vector of length n;
Let G represent a matrix of k rows and n columns; G is known as the Generator Matrix for the (n,k) code and is assumed to be composed from a P matrix and an identity matrix of k rows and k columns (Ik). P is a matrix having k rows and n−k columns, with elements having a value 0 or 1.
The Generator Matrix is defined by the equation:G=[P|Ik]
The code word v is generated by the equation:v=u·G
Implementing vector-matrix multiplication in digital circuits, in which all values are binary, is relatively simple. Each position vi in v is a sum of a set of bit positions within u, so that each vi is given by a linear equation. Since a Modulo-2 addition operation is equivalent to an XOR operation, each of the equations may be implemented by a series of XOR gates activated in parallel. It will be understood that for any given EDAC code, G is a fixed matrix and so the group of equations corresponding to the complete u·G operation can be implemented as circuitry that outputs elements vi as solutions of the equations. Due to the inherent speed of XOR gates, and using parallel processing, the u·G operation can typically be completed using one microprocessor cycle.
Typically, the decoding process of BCH codes uses more processing cycles than the encoding process. Decoding BCH codes comprises three distinct steps, processed respectively for each received vector r:
1. Syndrome calculation
2. Defining the error pattern
3. Correcting the erroneous bits
The first and third steps consume relatively few cycles. As will be explained below, the second step has the largest overhead and, therefore, any processing cycle reduction in this step can significantly increase the overall decoding speed.
Referring to the first step, a syndrome s is a vector of length m·t that indicates whether the received vector r is a code word. If the syndrome comprises only binary 0s, then r is a code word. Any other syndrome value indicates that r is not a code word.
The syndrome is calculated as follows:
A parity-check matrix, H, is derived from G by the equation:H=[In−k|PT]
where pT is the transpose of P.
Let r be a received vector (in the form of a row)
Then, by definition, the syndrome s of r is an (n−k) tuple given bys=r·HT=(s0, s1, s2, . . . , sn−k−1)  (1a)
An equivalent equation for the syndrome when r is in the form of a column is given by:
                    s        =                              H            ·            r                    =                      [                                                                                s                    0                                                                                                                    s                    1                                                                                                                    s                    2                                                                                                ⋮                                                                                                                                             s                                              n                        -                        k                        -                        1                                                                                                                  ]                                              (                  1          ⁢          b                )            
For a given G, H is predefined. Since H·r is a vector-matrix multiplication, it can be performed using a technique substantially similar to that described above (for encoding formula v=u·G), i.e., as circuitry outputting elements of s. The circuitry uses a similar number of microprocessor cycles to generate the elements.
In general, matrix H may be written in the following form, using a primitive Galois Field element α:
                    H        =                  [                                                    1                                            α                                                              α                  2                                                                              α                  3                                                            ⋯                                                              α                                      n                    -                    1                                                                                                      1                                                              (                                      α                    2                                    )                                                                                                  (                                          α                      2                                        )                                    2                                                                                                  (                                          α                      2                                        )                                    3                                                            ⋯                                                                                  (                                          α                      2                                        )                                                        n                    -                    1                                                                                                      1                                                              (                                      α                    3                                    )                                                                                                  (                                          α                      3                                        )                                    2                                                                                                  (                                          α                      3                                        )                                    3                                                            ⋯                                                                                  (                                          α                      3                                        )                                                        n                    -                    1                                                                                                      ⋮                                                                                                                                                                                                                                                                                                                                                                    ⋮                                                                    1                                                              (                                      α                                          2                      ⁢                      t                                                        )                                                                                                  (                                          α                                              2                        ⁢                        t                                                              )                                    2                                                                                                  (                                          α                                              2                        ⁢                        t                                                              )                                    3                                                            ⋯                                                                                  (                                          α                                              2                        ⁢                        t                                                              )                                                        n                    -                    1                                                                                ]                                    (        2        )            
wherein the entries in H are elements of a Galois Field GF(2m), expressed in terms of α.
For t-error-correcting BCH codes, every other row of H may be omitted, to give a reduced parity-check matrix H of the form:
                    H        =                  [                                                    1                                            α                                                              α                  2                                                                              α                  3                                                            ⋯                                                              α                                      n                    -                    1                                                                                                      1                                                              (                                      α                    3                                    )                                                                                                  (                                          α                      3                                        )                                    2                                                                                                  (                                          α                      3                                        )                                    3                                                            ⋯                                                                                  (                                          α                      3                                        )                                                        n                    -                    1                                                                                                      1                                                              (                                      α                    5                                    )                                                                                                  (                                          α                      5                                        )                                    2                                                                                                  (                                          α                      5                                        )                                    3                                                            ⋯                                                                                  (                                          α                      5                                        )                                                        n                    -                    1                                                                                                      ⋮                                                                                                                                                                                                                                                                                                                                                                    ⋮                                                                    1                                                              (                                      α                                                                  2                        ⁢                        t                                            -                      1                                                        )                                                                                                  (                                          α                                                                        2                          ⁢                          t                                                -                        1                                                              )                                    2                                                                                                  (                                          α                                                                        2                          ⁢                          t                                                -                        1                                                              )                                    3                                                            ⋯                                                                                  (                                          α                                                                        2                          ⁢                          t                                                -                        1                                                              )                                                        n                    -                    1                                                                                ]                                    (        3        )            
Since each element of H is equivalent to an m-tuple binary element column, the parity-check matrix H in a binary form has mt rows and n columns.
As is known in the art, elements of Galois Fields may be expressed as powers of α, as equivalent sums of powers of α, or as vectors. An example of equivalent representations of elements in GF(23) is shown in Table I.
TABLE IElements of GF(23)As a vectorAs a sumAs a power(0 0 0)0.1 + 0.α + 0.α2Undefined(1 0 0)1.1 + 0.α + 0.α2α0(0 1 0)0.1 + 1.α + 0.α2α1(0 0 1)0.1 + 0.α + 1.α2α2(1 1 0)1.1 + 1.α + 0.α2α3(1 1 1)1.1 + 1.α + 1.α2α4(1 0 1)1.1 + 0.α + 1.α2α5
After calculating the syndrome, the second step of BCH decoding uses the syndrome (the output of step 1) to locate and correct the erroneous bits. Processes known in the art for performing this step typically use a large number of processing cycles to determine coefficients of an error location polynomial σ from the syndrome components. The third step then finds the roots of σ, which give error positions in received vector r.
An alternative faster method, also known in the art, is to pre-define a look-up table, in which bit values of 1 in each row of the table give locations of erroneous bits.
The table used in this method has dimensions of 2mt rows by mt columns. The syndrome is assumed to be a single binary number, of length mt, which indexes the table, and each indexed row shows the error bits (as 1s) for the syndrome. Thus, for a (127, 113) code, the syndrome is 14 bits long, and the table is 214 rows by 14 columns. The table content for each row pointed to by the syndrome includes two pointers to two possible erroneous bits. Thus, the table size grows exponentially with mt and the memory resources needed for the table become prohibitive in typical microprocessor implementations.